package 牛客.动态规划;

public class BM66最长公共子串 {
    //不同于BM65，本题要求的公共子串需要连续
    public String LCS (String str1, String str2) {
        // write code here
        int[][] dp=new int[str1.length()+1][str2.length()+1];
        int maxlen=0;
        int endIndex=0;

        for (int i = 1; i <=str1.length() ; i++) {
            for (int j = 1; j <=str2.length() ; j++) {
                if (str1.charAt(i-1)==str2.charAt(j-1)) {
                    dp[i][j]=dp[i-1][j-1]+1;
                }
                if (dp[i][j]>maxlen) {
                    maxlen=dp[i][j];
                    endIndex=i;
                }
            }
        }

        return str1.substring(endIndex-maxlen,endIndex+1);


    }
}
